package com.zjsru.plan2024.oneday;

import java.util.HashMap;
import java.util.Map;

/**
 * 2671. 频率跟踪器
 * @Author: cookLee
 * @Date: 2024-03-21
 */
public class FrequencyTracker {

    /**
     * 主
     * \
     * 输入
     * ["FrequencyTracker", "add", "add", "hasFrequency"]
     * [[], [3], [3], [2]]
     * 输出
     * [null, null, null, true]
     * 解释
     * FrequencyTracker frequencyTracker = new FrequencyTracker();
     * frequencyTracker.add(3); // 数据结构现在包含 [3]
     * frequencyTracker.add(3); // 数据结构现在包含 [3, 3]
     * frequencyTracker.hasFrequency(2); // 返回 true ，因为 3 出现 2 次
     * \
     * @param args args
     */
    public static void main(String[] args) {
        FrequencyTracker frequencyTracker = new FrequencyTracker();
        frequencyTracker.add(3);
        frequencyTracker.add(3);
        System.out.println(frequencyTracker.hasFrequency(2));
    }

    /**
     * 限定数组长度
     */
    private final int N = 100001;

    /**
     * 数字出现频率计数
     */
    private final int[] freq;

    /**
     * 出现的各个频率计数
     */
    private final int[] freqCnt;

    /**
     * 使用一个空数组初始化 FrequencyTracker 对象。
     */
    public FrequencyTracker() {
        this.freq = new int[this.N];
        this.freqCnt = new int[this.N];
    }

    /**
     * 添加一个 number 到数据结构中。
     * 原来的频率-1，新的频率+1，比如说原来有1个3,现在又add了一个3，3的频率由1变成了2，那么频率1的数量就要-1，频率2的数量就要+1
     * @param number 编号
     */
    public void add(int number) {
        //先调整在freqCnt中的计数
        this.freqCnt[this.freq[number]]--;
        //增加数字的出现次数
        this.freq[number]++;
        this.freqCnt[this.freq[number]]++;

    }

    /**
     * 从数据结构中删除一个 number 。数据结构 可能不包含 number ，在这种情况下不删除任何内容。
     * 与添加同理
     * @param number 编号
     */
    public void deleteOne(int number) {
        if (this.freq[number] == 0) {
            return;
        }
        this.freqCnt[this.freq[number]]--;
        this.freq[number]--;
        this.freqCnt[this.freq[number]]++;
    }

    /**
     * 如果数据结构中存在出现 frequency 次的数字，则返回 true，否则返回 false
     *
     * @param frequency 频率
     * @return boolean
     */
    public boolean hasFrequency(int frequency) {
        return freqCnt[frequency] > 0;
    }


    //一个map记录val-出现次数1，3 表示节点1出现了三次
    Map<Integer, Integer> map = null;
    //另外一个map记录 出现次数-多少个节点这个出现次数,比如3，5，表示出现次数为3的节点有五个
    Map<Integer, Integer> freRec  = null;

    /**
     * 使用哈希表解决
     */
    public void FrequencyTracker2() {
        this.map = new HashMap<>();
        this.freRec = new HashMap<>();
    }

    /**
     * 添加
     *
     * @param number 编号
     */
    public void add2(int number) {
        //number目前出现的次数
        int cur = this.map.getOrDefault(number, 0);
        if (cur == 0) {
            this.map.put(number, 1);
            //出现次数为1的节点数量++；
            this.freRec.put(1, this.freRec.getOrDefault(1, 0) + 1);
        } else {
            //出现的数字加一
            this.map.put(number, cur + 1);
            //原来数字对应的频率减少
            this.freRec.put(cur, this.freRec.get(cur) - 1);
            //增加后的数字频率增加
            this.freRec.put(cur + 1, this.freRec.getOrDefault(cur + 1, 0) + 1);
        }
    }

    /**
     * 删除
     *
     * @param number 编号
     */
    public void deleteOne2(int number) {
        int cur = this.map.getOrDefault(number, 0);
        //cur==0表示这个数没有出现过
        if (cur != 0) {
            //数字删去
            this.map.put(number, this.map.get(number) - 1);
            //原来数字对应的频率减少
            this.freRec.put(cur, this.freRec.get(cur) - 1);
            //增加后的数字频率增加
            this.freRec.put(cur - 1, this.freRec.getOrDefault(cur - 1, 0) + 1);
        }
    }

    /**
     * 判断是否存在
     *
     * @param frequency 频率
     * @return boolean
     */
    public boolean hasFrequency2(int frequency) {
        return this.freRec.getOrDefault(frequency, 0) > 0;
    }

}
